package com.grape.dsaa.algorithm.sort.core;

import com.grape.dsaa.algorithm.sort.Sorter;

/**
 * 描述:冒泡排序
 * 算法的核心在于每次通过两两比较交换位置，选出剩余数组里最大（小）的数据元素放到数组尾部
 * @author: myx
 * @date: 2019-04-29
 * Copyright © 2019-grape. All rights reserved.
 */
public class BubbleSorter implements Sorter {

	/**
	 * 优化冒泡排序
	 * @param arr
	 */
	@Override
	public void sort(int[] arr) {
		if(arr == null || arr.length <= 1) {
			return;
		}
		
		//平均和最坏O(n^2)，最好O(n)
		for(int i=0; i<arr.length; i++) {
			boolean flag = false;
			for(int j=0; j<arr.length - i - 1; j++) {
				if(arr[j] > arr[j+1]) {
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
					flag = true;
				}
			}
			if(!flag){
				break;
			}
		}
 
	}

	/**
	 * 原始冒泡排序
	 * @param arr
	 */
	private void firstSort(int[] arr){
		if(arr == null || arr.length <= 1) {
			return;
		}

		//平均和最坏O(n^2)，最好O(n)
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr.length - i - 1; j++) {
				if(arr[j] > arr[j+1]) {
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
	}

}
